#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
 * @brief 
 * 字符串匹配算法
 * KMP 算法
 */

/**
 * @brief 
 * 计算prefix_table表
 * @param patten 
 * @param prefix 
 * @param n 
 */
void prefix_table(char patten[] , int prefix[] , int n)
{
    prefix[0] = 0;
    int len = 0;
    int i = 1;
    while ( i < n)
    {
        if (patten[i] == patten[len])
        {
            len++;
            prefix[i] = len;
            i++;
        }
        else
        {
            if (len > 0)
                len = prefix[len - 1];
            else
            {
                prefix[i] = len;
                i++;
            }
        }
    }
}

void move_prefix_table(int prefix_table[] , int len)
{
    for (int i = len - 1; i > 0; i--)
        prefix_table[i] = prefix_table[i-1];
    prefix_table[0] = -1;
    
}

int strStr(char * haystack, char * needle){
    if (needle == NULL || strlen(needle) == 0) return 0;
    if (strlen(needle) > strlen(haystack)) return -1;
    int result = -1;
    int n = strlen(needle);
    int prefix[n] = {0x00};
    prefix_table(needle,prefix,n);
    move_prefix_table(prefix,n);
    int m = strlen(haystack);
    int i = 0 , j = 0;
    while (i < m)
    {
        if (j == n - 1 && haystack[i] == needle[j])
        {
            printf("%d\n",i-j);
            result = i-j;
            break;
        }
        if (haystack[i] == needle[j])
        {
            i++; j++;
        }
        else
        {
            j = prefix[j];
            if (j == -1)
            {
                i++;j++;
            }
        }
    }
    return result;
}

int main(void)
{
    char str[] = "a";
    char son[] = "aa";
    int result = strStr(str,son);
    printf("result = %d\n",result);
    
    return 0;
}